Detecting a boundary crossing on a digital road map is of crucial importance for electronic toll systems based on global satellite navigation systems (GNSS) such as GPS, GLONASS, Galileo, etc. In such GNSS toll systems, vehicle-based onboard units (OBUs) continuously determine their own positions (“position fixes”), by of satellite navigation systems. Then positions are then compared decentrally in the OBUs or centrally in one or more server computers of the road toll system—to road segments of a digital road map (“map matching”) to determine the usage of a road or an area (e.g. city area) by a vehicle, and then to charge a toll. In order to determine the toll correctly, the entry into and exit from an area subject to a toll must be accurately determined. For this purpose, virtual boundaries, so-called “virtual gantries are defined on the digital road map,” the crossing of which is to be detected based on the continuously determined positions of a vehicle.
A variety of methods for solving this detection problem are known from the publications EP 1 696 208, EP 1 701 322, WO 95/14909, DE 101 55 501, WO 2004/025574, DE 10 2005 016 814 and EP 0 742 890 and are based on detection of the entry into certain regions (“geofencing”), a check of the sequence of areas traveled through or a continuous determination of the distance from a defined boundary point. All of these known methods have the disadvantage that they require very elaborate calculations and are thus ill-suited for real-time implementations on OBU processors with limited computational power, or due to position determination inaccuracies inherent in the system, they cannot provide reliable information about a boundary crossing if, for example, a driver comes into the vicinity of a boundary but turns around shortly before reaching it.